skip to main content
10.1145/1390630.1390649acmconferencesArticle/Chapter ViewAbstractPublication PagesisstaConference Proceedingsconference-collections
research-article

Dynamic recognition of synchronization operations for improved data race detection

Authors Info & Claims
Published:20 July 2008Publication History

ABSTRACT

Debugging multithreaded programs, which involves detection and identification of the cause of data races, has proved to be a hard problem. Although there has been significant amount of research on this topic, prior works rely on one important assumption - the debuggers must be aware of all the synchronization operations that take place during a program run. This assumption is a significant limitation as multithreaded programs, including the popular SPLASH-2 benchmark, have barriers and flag synchronizations implemented in the user code. We show that the lack of knowledge of these synchronization operations leads to unnecessary reporting of numerous races. Our experiments with SPLASH-2 benchmark suite show that 12-131 distinct segments in source code, on an average, give rise to well over 4 million dynamic instances of falsely reported races for these programs. We propose a dynamic software technique that identifies the user defined synchronizations exercised during a program run. This information not only helps avoids reporting of unnecessary races, but also helps a record/replay system to speedup the replay.

Our evaluation confirms that our synchronization detector is highly accurate with no false negatives and very few false positives. Thus, reporting of nearly all unnecessary races is avoided. Finally, we show that the knowledge of synchronization operations resulted in about 23% reduction in replay time.

References

  1. S.V. Adve, M.D. Hill, B.P. Miller, and R.H.B. Netzer. Detecting data races on weak memory systems. In Proceedings of the 18th International Symposium on Computer Architecture (ISCA), volume 19, pages 234--243, New York, NY, 1991. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. E. Artiaga, N. Navarro, X. Martorell, Y. Becerra, M. Gil, and A. Serra. Experiences on the implementation of parmacs macros using different multiprocessor operating system interfaces.Google ScholarGoogle Scholar
  3. D.F. Bacon and S.C. Goldstein. Hardware-assisted replay of multiprocessor programs. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 194--206, New York, NY, USA, 1991. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. S. Bhansali, W.-K. Chen, S. de Jong, A. Edwards, R. Murray, M. Drinić, D. Mihocka, and J. Chau. Framework for instruction-level tracing and analysis of program executions. In VEE '06: Proceedings of the 2nd international conference on Virtual execution environments, pages 154--163, New York, NY, USA, 2006. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: preventing data races and deadlocks. In OOPSLA '02: Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 211--230, New York, NY, USA, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. J.-D. Choi, B.P. Miller, and R.H.B. Netzer. Techniques for debugging parallel programs with flowback analysis. ACM Trans. Program. Lang. Syst., 13(4):491--530, 1991. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. M. Christiaens and K. D. Bosschere. Trade, a topological approach to on-the-fly race detection in java programs. In JVM'01: Proceedings of the Java™ Virtual Machine Research and Technology Symposium on Java™ Virtual Machine Research and Technology Symposium, pages 15--15, Berkeley, CA, USA, 2001. USENIX Association. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. A. Dinning and E. Schonberg. Detecting access anomalies in programs with critical sections. In PADD '91: Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, pages 85--96, New York, NY, USA, 1991. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. C. Flanagan and S. N. Freund. Type-based race detection for Java. ACM SIGPLAN Notices, 35(5):219--232, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. C. Flanagan and S. N. Freund. Atomizer: a dynamic atomicity checker for multithreaded programs. SIGPLAN Not., 39(1):256--267, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. R. Gupta. The fuzzy barrier: a mechanism for high speed synchronization of processors. In ASPLOS-III: Proceedings of the third international conference on Architectural support for programming languages and operating systems, pages 54--63, New York, NY, USA, 1989. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. B. Krena, Z. Letko, R. Tzoref, S. Ur, and T. Vojnar. Healing data races on-the-fly. In PADTAD '07: Proceedings of the 2007 ACM workshop on Parallel and distributed systems: testing and debugging, pages 54--64, New York, NY, USA, 2007. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, 1978. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. SIGPLAN Not., 40(6):190--200, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. P. Magnusson, A. Landin, and E. Hagersten. Queue locks on cache coherent multiprocessors. pages 165--171. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. J. Mellor-Crummey. On-the-fly detection of data races for programs with nested fork-join parallelism. In Supercomputing '91: Proceedings of the 1991 ACM/IEEE conference on Supercomputing, pages 24--33, New York, NY, USA, 1991. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. J.M. Mellor-Crummey and M.L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst., 9(1):21--65, 1991. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. S. Narayanasamy, C. Pereira, and B. Calder. Recording shared memory dependencies using strata. In ASPLOS-XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, pages 229--240, New York, NY, USA, 2006. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. S. Narayanasamy, G. Pokam, and B. Calder. Bugnet: Continuously recording program execution for deterministic replay debugging. In ISCA '05: Proceedings of the 32nd annual international symposium on Computer Architecture, pages 284--295, Washington, DC, USA, 2005. IEEE Computer Society. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically classifying benign and harmful data racesallusing replay analysis. In PLDI '07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pages 22--31, New York, NY, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. N. Nethercote and J. Seward. How to shadow every byte of memory used by a program. In VEE '07: Proceedings of the 3rd international conference on Virtual execution environments, pages 65--74, New York, NY, USA, 2007. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. R. H. B. Netzer. Optimal tracing and replay for debugging shared-memory parallel programs. In PADD '93: Proceedings of the 1993 ACM/ONR workshop on Parallel and distributed debugging, pages 1--11, New York, NY, USA, 1993. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In PPoPP '03: Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 167--178, New York, NY, USA, 2003. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. V. Project. Helgrind, a data race detector. In http://valgrind.org/docs/manual/hg-manual.html, 2003.Google ScholarGoogle Scholar
  25. M. Ronsse and K.D. Bosschere. Recplay: a fully integrated practical record/replay system. ACM Trans. Comput. Syst., 17(2):133--152, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Y. Saito. Jockey: a user-space library for record-replay debugging. In AADEBUG'05: Proceedings of the sixth international symposium on Automated analysis-driven debugging, pages 69--76, New York, NY, USA, 2005. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. A. Sasturkar, R. Agarwal, L. Wang, and S. D. Stoller. Automated type-based analysis of data races and atomicity. In PPoPP '05: Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 83--94, New York, NY, USA, 2005. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: a dynamic data race detector for multi-threaded programs. In SOSP '97: Proceedings of the sixteenth ACM symposium on Operating systems principles, pages 27--37, New York, NY, USA, 1997. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. C. von Praun and T. R. Gross. Object race detection. In OOPSLA '01: Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, pages 70--82, New York, NY, USA, 2001. ACM. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta. The SPLASH-2 programs: Characterization and methodological considerations. In Proceedings of the 22th International Symposium on Computer Architecture, pages 24--36, Santa Margherita Ligure, Italy, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. M. Xu, R. Bodik, and M. D. Hill. A flight data recorder for enabling full-system multiprocessor recorder for enabling full-system multiprocessor deterministic replay. In ISCA '03: Proceedings of the 30th annual international symposium on Computer architecture, pages 122--135, New York, NY, USA, 2003. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. Y. Yu, T. Rodeheffer, and W. Chen. Racetrack: efficient detection of data race conditions via adaptive tracking. In SOSP '05: Proceedings of the twentieth ACM symposium on Operating systems principles, pages 221--234, New York, NY, USA, 2005. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Dynamic recognition of synchronization operations for improved data race detection

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in
    • Published in

      cover image ACM Conferences
      ISSTA '08: Proceedings of the 2008 international symposium on Software testing and analysis
      July 2008
      324 pages
      ISBN:9781605580500
      DOI:10.1145/1390630

      Copyright © 2008 ACM

      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 20 July 2008

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      Overall Acceptance Rate58of213submissions,27%

      Upcoming Conference

      ISSTA '24

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader